package leetcode.topinterviewquestions;

public class Problem_0230_KthSmallestElementInBST {

    public static int kthSmallest(TreeNode head, int k) {
        if (head == null) {
            return -1;
        }
        TreeNode cur = head;
        TreeNode mostRight = null;
        int index = 1;
        while (cur != null) {
            mostRight = cur.left;
            if (mostRight != null) {
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            if (index++ == k) {
                return cur.val;
            }
            cur = cur.right;
        }
        return -1;
    }

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

}
